#include <vector>
#include <unordered_map>
#include <string>
#include <algorithm>
#include <iostream>
#include <string_view>
#include <cstring>

using namespace std;

class Solution
{
public:
    // 运用字典树
    vector<int> sumPrefixScores(vector<string> &words)
    {
        class TrieNode
        {
        public:
            using TrieNodePtr = TrieNode *;
            TrieNodePtr child[26];
            int count;

            TrieNode()
            {
                this->count = 0;
                memset(this->child, 0, 26 * sizeof(TrieNodePtr));
            }

            ~TrieNode()
            {
                for (int i = 0; i < 26; ++i)
                {
                    delete this->child[i];
                    this->child[i] = nullptr;
                }
            }
        };
        TrieNode::TrieNodePtr root = new TrieNode();
        for (auto &word : words)
        {
            TrieNode::TrieNodePtr cur = root;
            for (auto c : word)
            {
                if (cur->child[c - 'a'] == nullptr)
                {
                    cur->child[c - 'a'] = new TrieNode();
                }
                cur = cur->child[c - 'a'];
                ++cur->count;
            }
        }

        int n = words.size();
        vector<int> answer(n, 0);
        for(int i = 0;i < n;++i)
        {
            string& word = words[i];
            TrieNode::TrieNodePtr cur = root;
            for (auto c : word)
            {
                cur = cur->child[c - 'a'];
                answer[i] += cur->count;
            }
        }

        delete root;
        return answer;
    }

    // 超时
    vector<int> sumPrefixScores(vector<string> &words)
    {
        vector<string_view> ss(words.begin(), words.end());
        sort(ss.begin(), ss.end());
        unordered_map<string_view, int> prefixScore;
        unordered_map<string_view, int> wordPrefixesTotalScore;
        this->n = ss.size();

        for (int i = 0; i < this->n; ++i)
        {
            if (wordPrefixesTotalScore.count(ss[i]))
            {
                continue;
            }
            int strLen = ss[i].size();
            int totalScore = 0;
            int left = i;
            int right = i;
            for (int j = strLen; j >= 1; --j)
            {
                string_view prefix = ss[i].substr(0, j);
                if (prefixScore.count(prefix))
                {
                    totalScore += prefixScore[prefix];
                }
                else
                {
                    int score = getPrefixScoreInOrderedSeq(prefix, ss, left, right, prefixScore);
                    totalScore += score;
                }
            }
            wordPrefixesTotalScore[ss[i]] = totalScore;
            string_view last = ss[i];
            for (int j = strLen - 1; j >= 1; --j)
            {
                string_view sub = ss[i].substr(0, j);
                if (!wordPrefixesTotalScore.count(sub))
                {
                    wordPrefixesTotalScore[sub] = wordPrefixesTotalScore[last] - prefixScore[last];
                }
                last = sub;
            }
        }

        vector<int> answer(this->n);
        for (int i = 0; i < this->n; ++i)
        {
            answer[i] = wordPrefixesTotalScore[words[i]];
        }
        return answer;
    }

private:
    int n = 0;

    int getPrefixScoreInOrderedSeq(string_view &prefix, vector<string_view> &words, int &leftIndex, int &rightIndex, unordered_map<string_view, int> &prefixScore)
    {
        int score = rightIndex - leftIndex + 1;
        int len = prefix.size();
        for (int i = leftIndex - 1; i >= 0; --i)
        {
            if (len > words[i].size())
            {
                break;
            }
            if (prefix == words[i].substr(0, len))
            {
                leftIndex = i;
                ++score;
            }
            else
            {
                break;
            }
        }
        for (int i = rightIndex + 1; i < this->n; ++i)
        {
            if (len > words[i].size())
            {
                break;
            }
            if (prefix == words[i].substr(0, len))
            {
                rightIndex = i;
                ++score;
            }
            else
            {
                break;
            }
        }
        prefixScore[prefix] = score;
        return score;
    }
};

int main()
{
    vector<string> input = {"abc", "ab", "bc", "b"};
    Solution s;
    auto ans = s.sumPrefixScores(input);
    for (auto i : ans)
    {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}